Scalable Underapproximation for the Stochastic Reach-Avoid Problem for High-Dimensional LTI Systems using Fourier Transforms

摘要

We present a scalable underapproximation of the terminal hitting timestochastic reach-avoid probability at a given initial condition, forverification of high-dimensional stochastic LTI systems. While severalapproximation techniques have been proposed to alleviate the curse ofdimensionality associated with dynamic programming, these techniques arelimited and cannot handle larger, more realistic systems. We present a scalablemethod that uses Fourier transforms to compute an underapproximation of thereach-avoid probability for systems with disturbances with arbitraryprobability densities. We characterize sufficient conditions forBorel-measurability of the value functions. We exploit fixed control sequencesparameterized by the initial condition (an open-loop control policy) togenerate the underapproximation. For Gaussian disturbances, theunderapproximation can be obtained using existing efficient algorithms bysolving a convex optimization problem. Our approach produces non-trivial lowerbounds and is demonstrated on a chain of integrators with 40 states.